<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Строки (hard)</h2>
<ol>
  <li>Хеши</li>
  <ol>
    <li>Полиномиальный хеш</li>
    <li>Сравненение на равенство за O(1)</li>
    <li>Сравненение на больше-меньше за O(logn)</li>
  </ol></li>
  <li>Суффиксный массив</li>
  <ol>
    <li>Построение за O(nlog<sup>2</sup>n). Оптимизация = MergeSort.</li>
    <li>Построение за O(nlogn). Оптимизация = Выйти, если не было изменений.</li>
    <li>Делаем сортировку устойчивой.</li>
    <li>Построение за O(n) (Каркайнен-Сандерс)</li>
    <li>Алгоритм Касаи: поиск LCP соседних за O(n)</li>
    <li>LCP(i,j) = RMQ(p<sub>i</sub>,p<sub>j</sub>)</li>
  </ol></li>
  <li>Суффиксное дерево</li>
  <ol>
    <li>Несжатое. Построение за O(n<sup>2</sup>) и O(n<sup>2</sup> + n&Sigma;) памяти</li>
    <li>Сжатое. Построение за O(n<sup>2</sup>) и O(n&Sigma;) памяти</li>
    <li>Укконен. Описание алгоритма, особенности реализации, доказательство времени работы.</li>
  </ol></li>
  <li>Суффиксный автомат</li>
  <ol>
    <li>Правые контексты, их изменение при дописовании в конце строки символа</li>
    <li>Суффиксные ссылки, путь от конца до корня из суффиксных ссылок --- все суффиксы строки</li>
    <li>Сам алгоритм, раздвоение вершины, перенос суффиксных ссылок</li>
    <li>Доказательство времени работы O(n).</li>
  </ol></li>
</ol>
